//package chapter12.jsjf;
//
//import chapter10.jsjf.exceptions.EmptyCollectionException;
//import chapter11.jsjf.LinkedBinaryTree;
//
//
///**
// * LinkedHeap implements a heap.
// *
// * @author Lewis and Chase
// * @version 4.0
// */
//public class LinkedHeap<T extends Comparable> extends LinkedBinaryTree<T> implements HeapADT<T>
//{
//    public HeapNode<T> lastNode;
//
//    public LinkedHeap()
//    {
//        super();
//    }
//
//    /**
//     * Adds the specified element to this heap in the appropriate
//     * position according to its key value.
//     *
//     * @param obj the element to be added to the heap
//     */
//    @Override
//    public void addElement(T obj)
//    {
//        HeapNode<T> node = new HeapNode<T>(obj);
//
//        if (root == null)
//            root=node;
//        else
//        {
//            HeapNode<T> nextParent = getNextParentAdd();
//            if (nextParent.getLeft() == null)
//                nextParent.setLeft(node);
//            else
//                nextParent.setRight(node);
//
//            node.setParent(nextParent);
//        }
//        lastNode = node;
//        modCount++;
//
//        if (size() > 1)
//            heapifyAdd();
//    }
//
//    /**
//     * Returns the node that will be the parent of the new node
//     *
//     * @return the node that will be the parent of the new node
//     */
//    private HeapNode<T> getNextParentAdd()
//    {
//        HeapNode<T> result = lastNode;
//
//        while ((result != root) && (result.getParent().getLeft() != result))
//            result = result.getParent();
//
//        if (result != root)
//            if (result.getParent().getRight() == null)
//                result = result.getParent();
//            else
//            {
//                result = (HeapNode<T>)result.getParent().getRight();
//                while (result.getLeft() != null)
//                    result = (HeapNode<T>)result.getLeft();
//            }
//        else
//            while (result.getLeft() != null)
//                result = (HeapNode<T>)result.getLeft();
//
//        return result;
//    }
//
//    /**
//     * Reorders this heap after adding a node.
//     */
//    private void heapifyAdd()
//    {
//        T temp;
//        HeapNode<T> next = lastNode;
//
//        temp = next.getElement();
//
//        while ((next != root) &&
//			(((Comparable)temp).compareTo(next.getParent().getElement()) < 0))
//        {
//            next.setElement(next.getParent().getElement());
//            next = next.parent;
//        }
//        next.setElement(temp);
//    }
//
//    /**
//     * Remove the element with the lowest value in this heap and
//     * returns a reference to it. Throws an EmptyCollectionException
//     * if the heap is empty.
//     *
//     * @return the element with the lowest value in this heap
//     * @throws EmptyCollectionException if the heap is empty
//     */
//    @Override
//    public T removeMin() throws EmptyCollectionException
//    {
//        if (isEmpty())
//            throw new EmptyCollectionException("LinkedHeap");
//
//        T minElement =  root.getElement();
//
//        if (size() == 1)
//        {
//            root = null;
//            lastNode = null;
//        }
//        else
//        {
//            HeapNode<T> nextLast = getNewLastNode();
//            if (lastNode.getParent().getLeft() == lastNode)
//                lastNode.getParent().setLeft(null);
//            else
//                lastNode.getParent().setRight(null);
//
//            ((HeapNode<T>)root).setElement(lastNode.getElement());
//            lastNode = nextLast;
//            heapifyRemove();
//        }
//
//        modCount++;
//
//        return minElement;
//    }
//
//    /**
//     * Reorders this heap after removing the root element.
//     */
//    private void heapifyRemove()
//    {
//        T temp;
//        HeapNode<T> node = (HeapNode<T>)root;
//        HeapNode<T> left = (HeapNode<T>)node.getLeft();
//        HeapNode<T> right = (HeapNode<T>)node.getRight();
//        HeapNode<T> next;
//
//        if ((left == null) && (right == null))
//            next = null;
//        else if (right == null)
//            next = left;
//        else if (((Comparable)left.getElement()).compareTo(right.getElement()) < 0)
//            next = left;
//        else
//            next = right;
//
//        temp = node.getElement();
//        while ((next != null) &&
//			(((Comparable)next.getElement()).compareTo(temp) < 0))
//        {
//            node.setElement(next.getElement());
//            node = next;
//            left = (HeapNode<T>)node.getLeft();
//            right = (HeapNode<T>)node.getRight();
//
//            if ((left == null) && (right == null))
//                next = null;
//            else if (right == null)
//                next = left;
//            else if (((Comparable)left.getElement()).compareTo(right.getElement()) < 0)
//                next = left;
//            else
//                next = right;
//        }
//        node.setElement(temp);
//    }
//
//    /**
//     * Returns the node that will be the new last node after a remove.
//     *
//     * @return the node that willbe the new last node after a remove
//     */
//    private HeapNode<T> getNewLastNode()
//    {
//        HeapNode<T> result = lastNode;
//
//        while ((result != root) && (result.getParent().getLeft() == result))
//            result = result.getParent();
//
//        if (result != root)
//            result = (HeapNode<T>)result.getParent().getLeft();
//
//        while (result.getRight() != null)
//            result = (HeapNode<T>)result.getRight();
//
//        return result;
//    }
//
//    /**
//     * Returns the element with the lowest value in this heap.
//     * Throws an EmptyCollectionException if the heap is empty.
//     *
//     * @return the element with the lowest value in this heap
//     * @throws EmptyCollectionException if the heap is empty
//     */
//    @Override
//    public T findMin() throws EmptyCollectionException
//    {
//        if (isEmpty())
//            throw new EmptyCollectionException("LinkedHeap");
//
//        return root.getElement();
//    }
//}
//
